ebab7d0da53c51438720d60c6e2e467c - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Single-parameter utility</title>

</head>

Single-parameter utility

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">In <a href="Mechanism_design" title="Mechanism design">mechanism design</a>, an agent is said to have single-parameter utility if his valuation of the possible outcomes can be represented by a single number. For example, in an <a href="Auction" title="Auction">auction</a> for a single item, the utilities of all agents are single-parametric, since they can be represented by their monetary evaluation of the item. In contrast, in a <a href="Combinatorial_auction" title="Combinatorial auction">combinatorial auction</a> for two or more related items, the utilities are usually not single-parametric, since they are usually represented by their evaluations to all possible bundles of items.

<div class="mw-heading mw-heading2"><h2 id="Notation">Notation</h2></div>

There is a set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> of possible outcomes.

There are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> agents which have different valuations for each outcome.

In general, each agent can assign a different and unrelated value to every outcome in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy">.

In the special case of single-parameter utility, each agent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> has a publicly known outcome <a href="Subset" title="Subset">proper subset</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W_{i}\subset X}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W_{i}\subset X}</annotation>

</semantics>

</math><img src="./2c6d6849aea4b484a02747693e3a9703f969c27f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.072ex; height:2.509ex;" alt="{\displaystyle W_{i}\subset X}" loading="lazy"> which are the "winning outcomes" for agent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> (e.g., in a single-item auction, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W_{i}}</annotation>

</semantics>

</math><img src="./7301a4cfd04d4f5db4549fdf23746a0d2ce9f387.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.993ex; height:2.509ex;" alt="{\displaystyle W_{i}}" loading="lazy"> contains the outcome in which agent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> wins the item).

For every agent, there is a number <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}}</annotation>

</semantics>

</math><img src="./7dffe5726650f6daac54829972a94f38eb8ec127.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.927ex; height:2.009ex;" alt="{\displaystyle v_{i}}" loading="lazy"> which represents the "winning-value" of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">. The agent's valuation of the outcomes in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> can take one of two values:<a href="#cite_note-agt07-1">[1]</a>: 228

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}}</annotation>

</semantics>

</math><img src="./7dffe5726650f6daac54829972a94f38eb8ec127.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.927ex; height:2.009ex;" alt="{\displaystyle v_{i}}" loading="lazy"> for each outcome in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W_{i}}</annotation>

</semantics>

</math><img src="./7301a4cfd04d4f5db4549fdf23746a0d2ce9f387.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.993ex; height:2.509ex;" alt="{\displaystyle W_{i}}" loading="lazy">;</li>

<li>0 for each outcome in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X\setminus W_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X\setminus W_{i}}</annotation>

</semantics>

</math><img src="./df8b67d725e3df62f4dfffc6ed826ca0709b6f03.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.168ex; height:2.843ex;" alt="{\displaystyle X\setminus W_{i}}" loading="lazy">.</li></ul>

The vector of the winning-values of all agents is denoted by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy">.

For every agent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">, the vector of all winning-values of the other agents is denoted by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{-i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{-i}}</annotation>

</semantics>

</math><img src="./2df94fa133d3a9d311b910092b780cf46418c3a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.206ex; height:2.009ex;" alt="{\displaystyle v_{-i}}" loading="lazy">. So <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\equiv (v_{i},v_{-i})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\equiv (v_{i},v_{-i})}</annotation>

</semantics>

</math><img src="./f9237f4bfb11b6f1ce5001bb295c1873d2031de6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.202ex; height:2.843ex;" alt="{\displaystyle v\equiv (v_{i},v_{-i})}" loading="lazy">.

A <a href="Social_choice" class="mw-redirect" title="Social choice">social choice</a> function is a function that takes as input the value-vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> and returns an outcome <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in X}</annotation>

</semantics>

</math><img src="./3e580967f68f36743e894aa7944f032dda6ea01d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.15ex; height:2.176ex;" alt="{\displaystyle x\in X}" loading="lazy">. It is denoted by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{Outcome}}(v)}">

<mtext>Outcome</mtext>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Outcome}}(v)}</annotation>

</semantics>

</math><img src="./e6c034bc46dcb60aefca5fc28edbb189558dfd2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.105ex; height:2.843ex;" alt="{\displaystyle {\text{Outcome}}(v)}" loading="lazy"> or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{Outcome}}(v_{i},v_{-i})}">

<mtext>Outcome</mtext>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Outcome}}(v_{i},v_{-i})}</annotation>

</semantics>

</math><img src="./2a3f0cfeb76f257de2bbac906d01627f3efd141a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.145ex; height:2.843ex;" alt="{\displaystyle {\text{Outcome}}(v_{i},v_{-i})}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Monotonicity">Monotonicity</h2></div>

The <a href="Monotonicity_(mechanism_design)#wmon" title="Monotonicity (mechanism design)">weak monotonicity property</a> has a special form in single-parameter domains. A social choice function is weakly-monotonic if for every agent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> and every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i},v_{i}',v_{-i}}">

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i},v_{i}',v_{-i}}</annotation>

</semantics>

</math><img src="./1fdf6513224d91290513ba17dc10f401a1deb92d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.128ex; height:2.843ex;" alt="{\displaystyle v_{i},v_{i}',v_{-i}}" loading="lazy">, if:

<mtext>Outcome</mtext>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Outcome}}(v_{i},v_{-i})\in W_{i}}</annotation>

</semantics>

</math><img src="./fcb960a22f4dec8eebb30fc1c864daf3e0870dd3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.979ex; height:2.843ex;" alt="{\displaystyle {\text{Outcome}}(v_{i},v_{-i})\in W_{i}}" loading="lazy"> and</dd>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v'_{i}\geq v_{i}>0}</annotation>

</semantics>

</math><img src="./bc1616be560689e15212d2ccc4afccc259e3d9db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.214ex; height:2.843ex;" alt="{\displaystyle v'_{i}\geq v_{i}>0}" loading="lazy"> then:</dd>

<mtext>Outcome</mtext>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Outcome}}(v'_{i},v_{-i})\in W_{i}}</annotation>

</semantics>

</math><img src="./b12b3845e903431c4ecabba423608ba45774d742.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:22.979ex; height:3.009ex;" alt="{\displaystyle {\text{Outcome}}(v'_{i},v_{-i})\in W_{i}}" loading="lazy"></dd></dl>

I.e, if agent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> wins by declaring a certain value, then he can also win by declaring a higher value (when the declarations of the other agents are the same).

The monotonicity property can be generalized to randomized mechanisms, which return a probability-distribution over the space <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy">.<a href="#cite_note-agt07-1">[1]</a>: 334 The WMON property implies that for every agent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> and every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i},v_{i}',v_{-i}}">

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i},v_{i}',v_{-i}}</annotation>

</semantics>

</math><img src="./1fdf6513224d91290513ba17dc10f401a1deb92d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.128ex; height:2.843ex;" alt="{\displaystyle v_{i},v_{i}',v_{-i}}" loading="lazy">, the function:

<mtext>Outcome</mtext>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pr[{\text{Outcome}}(v_{i},v_{-i})\in W_{i}]}</annotation>

</semantics>

</math><img src="./b538226e27317ed54ffffaa15fb7de78c32035e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.767ex; height:2.843ex;" alt="{\displaystyle \Pr[{\text{Outcome}}(v_{i},v_{-i})\in W_{i}]}" loading="lazy"></dd></dl>

is a weakly-increasing function of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}}</annotation>

</semantics>

</math><img src="./7dffe5726650f6daac54829972a94f38eb8ec127.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.927ex; height:2.009ex;" alt="{\displaystyle v_{i}}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Critical_value">Critical value</h3></div>

For every weakly-monotone social-choice function, for every agent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> and for every vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{-i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{-i}}</annotation>

</semantics>

</math><img src="./2df94fa133d3a9d311b910092b780cf46418c3a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.206ex; height:2.009ex;" alt="{\displaystyle v_{-i}}" loading="lazy">, there is a critical value <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i}(v_{-i})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i}(v_{-i})}</annotation>

</semantics>

</math><img src="./8dcd2a2b22e1eb244e50b53f555f4ee01586e8c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.822ex; height:2.843ex;" alt="{\displaystyle c_{i}(v_{-i})}" loading="lazy">, such that agent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> wins if-and-only-if his bid is at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i}(v_{-i})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i}(v_{-i})}</annotation>

</semantics>

</math><img src="./8dcd2a2b22e1eb244e50b53f555f4ee01586e8c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.822ex; height:2.843ex;" alt="{\displaystyle c_{i}(v_{-i})}" loading="lazy">.

For example, in a <a href="Second-price_auction" class="mw-redirect" title="Second-price auction">second-price auction</a>, the critical value for agent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> is the highest bid among the other agents.

In single-parameter environments, deterministic truthful mechanisms have a very specific format.<a href="#cite_note-agt07-1">[1]</a>: 334 Any deterministic truthful mechanism is fully specified by the set of functions c. Agent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> wins if and only if his bid is at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i}(v_{-i})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i}(v_{-i})}</annotation>

</semantics>

</math><img src="./8dcd2a2b22e1eb244e50b53f555f4ee01586e8c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.822ex; height:2.843ex;" alt="{\displaystyle c_{i}(v_{-i})}" loading="lazy">, and in that case, he pays exactly <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i}(v_{-i})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i}(v_{-i})}</annotation>

</semantics>

</math><img src="./8dcd2a2b22e1eb244e50b53f555f4ee01586e8c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.822ex; height:2.843ex;" alt="{\displaystyle c_{i}(v_{-i})}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Deterministic_implementation">Deterministic implementation</h2></div>

It is known that, in any domain, <a href="Monotonicity_(mechanism_design)#wmon" title="Monotonicity (mechanism design)">weak monotonicity</a> is a necessary condition for implementability. I.e, a social-choice function can be implemented by a <a href="Truthful_mechanism" class="mw-redirect" title="Truthful mechanism">truthful mechanism</a>, only if it is weakly-monotone.

In a single-parameter domain, weak monotonicity is also a sufficient condition for implementability. I.e, for every weakly-monotonic social-choice function, there is a deterministic <a href="Truthful_mechanism" class="mw-redirect" title="Truthful mechanism">truthful mechanism</a> that implements it. This means that it is possible to implement various non-linear social-choice functions, e.g. maximizing the sum-of-squares of values or the min-max value.

The mechanism should work in the following way:<a href="#cite_note-agt07-1">[1]</a>: 229

<ul><li>Ask the agents to reveal their valuations, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy">.</li>

<li>Select the outcome based on the social-choice function: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x={\text{Outcome}}[v]}">

<mtext>Outcome</mtext>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x={\text{Outcome}}[v]}</annotation>

</semantics>

</math><img src="./b0ad3164f320ea3503d116555949908d27308a2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.018ex; height:2.843ex;" alt="{\displaystyle x={\text{Outcome}}[v]}" loading="lazy">.</li>

<li>Every winning agent (every agent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in W_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in W_{i}}</annotation>

</semantics>

</math><img src="./2ef3d90320b82ecc399840fe15a52173882fd386.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.164ex; height:2.509ex;" alt="{\displaystyle x\in W_{i}}" loading="lazy">) pays a price equal to the critical value: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{Price}}_{i}(x,v_{-i})=-c_{i}(v_{-i})}">

<msub>

<mtext>Price</mtext>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Price}}_{i}(x,v_{-i})=-c_{i}(v_{-i})}</annotation>

</semantics>

</math><img src="./0b30cd90348f962bce37ead9a1647171f30a462d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.113ex; height:2.843ex;" alt="{\displaystyle {\text{Price}}_{i}(x,v_{-i})=-c_{i}(v_{-i})}" loading="lazy">.</li>

<li>Every losing agent (every agent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\notin W_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\notin W_{i}}</annotation>

</semantics>

</math><img src="./0797865592617792ff1d27e70221c284c8b901a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.164ex; height:2.676ex;" alt="{\displaystyle x\notin W_{i}}" loading="lazy">) pays nothing: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{Price}}_{i}(x,v_{-i})=0}">

<msub>

<mtext>Price</mtext>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Price}}_{i}(x,v_{-i})=0}</annotation>

</semantics>

</math><img src="./2376fe9d933d05b2c5b3814c0cfa18c756ec52eb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.645ex; height:2.843ex;" alt="{\displaystyle {\text{Price}}_{i}(x,v_{-i})=0}" loading="lazy">.</li></ul>

This mechanism is truthful, because the net utility of each agent is:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}-c_{i}(v_{-i})}</annotation>

</semantics>

</math><img src="./4200d228d27c69679858dfe364aadd6661681523.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.589ex; height:2.843ex;" alt="{\displaystyle v_{i}-c_{i}(v_{-i})}" loading="lazy"> if he wins;</li>

<li>0 if he loses.</li></ul>

Hence, the agent prefers to win if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}>c_{-i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}>c_{-i}}</annotation>

</semantics>

</math><img src="./25ecf1969d4de73d4b1232d10bd716cb5a8d4458.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.111ex; height:2.176ex;" alt="{\displaystyle v_{i}>c_{-i}}" loading="lazy"> and to lose if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}<c_{-i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}<c_{-i}}</annotation>

</semantics>

</math><img src="./b861d3f1ddaf443502c05cec243ee30a2207cff5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.111ex; height:2.176ex;" alt="{\displaystyle v_{i}<c_{-i}}" loading="lazy">, which is exactly what happens when he tells the truth.

<div class="mw-heading mw-heading2"><h2 id="Randomized_implementation">Randomized implementation</h2></div>

A randomized mechanism is a probability-distribution on deterministic mechanisms. A randomized mechanism is called truthful-in-expectation if truth-telling gives the agent a largest <a href="Expected_value" title="Expected value">expected value</a>.

In a randomized mechanism, every agent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> has a probability of winning, defined as:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mtext>Outcome</mtext>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{i}(v_{i},v_{-i}):=\Pr[{\text{Outcome}}(v_{i},v_{-i})\in W_{i}]}</annotation>

</semantics>

</math><img src="./40fedd3344c850f501c7ecea01b3869604265e7b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:40.952ex; height:2.843ex;" alt="{\displaystyle w_{i}(v_{i},v_{-i}):=\Pr[{\text{Outcome}}(v_{i},v_{-i})\in W_{i}]}" loading="lazy"></dd></dl>

and an expected payment, defined as:

</mrow>

<msub>

<mtext>Payment</mtext>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} [{\text{Payment}}_{i}(v_{i},v_{-i})]}</annotation>

</semantics>

</math><img src="./ae7a6e00940656cbd1f9dbf0e32936751285e6f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.758ex; height:2.843ex;" alt="{\displaystyle \mathbb {E} [{\text{Payment}}_{i}(v_{i},v_{-i})]}" loading="lazy"></dd></dl>

In a single-parameter domain, a randomized mechanism is truthful-in-expectation if-and-only if:<a href="#cite_note-agt07-1">[1]</a>: 232

<ul><li>The probability of winning, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{i}(v_{i},v_{-i})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{i}(v_{i},v_{-i})}</annotation>

</semantics>

</math><img src="./68033b419938603dee66c7bea8ac952920b7df1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.44ex; height:2.843ex;" alt="{\displaystyle w_{i}(v_{i},v_{-i})}" loading="lazy">, is a weakly-increasing function of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}}</annotation>

</semantics>

</math><img src="./7dffe5726650f6daac54829972a94f38eb8ec127.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.927ex; height:2.009ex;" alt="{\displaystyle v_{i}}" loading="lazy">;</li>

<li>The expected payment of an agent is:</li></ul>

</mrow>

<msub>

<mtext>Payment</mtext>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} [{\text{Payment}}_{i}(v_{i},v_{-i})]=v_{i}\cdot w_{i}(v_{i},v_{-i})-\int _{0}^{v_{i}}w_{i}(t,v_{-i})dt}</annotation>

</semantics>

</math><img src="./5b1710763aa6d90971c1b8ab534bc06a6c40e419.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:56.657ex; height:5.843ex;" alt="{\displaystyle \mathbb {E} [{\text{Payment}}_{i}(v_{i},v_{-i})]=v_{i}\cdot w_{i}(v_{i},v_{-i})-\int _{0}^{v_{i}}w_{i}(t,v_{-i})dt}" loading="lazy"></dd></dl>

Note that in a deterministic mechanism, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{i}(v_{i},v_{-i})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{i}(v_{i},v_{-i})}</annotation>

</semantics>

</math><img src="./68033b419938603dee66c7bea8ac952920b7df1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.44ex; height:2.843ex;" alt="{\displaystyle w_{i}(v_{i},v_{-i})}" loading="lazy"> is either 0 or 1, the first condition reduces to weak-monotonicity of the Outcome function and the second condition reduces to charging each agent his critical value.

<div class="mw-heading mw-heading2"><h2 id="Single-parameter_vs._multi-parameter_domains">Single-parameter vs. multi-parameter domains</h2></div>

When the utilities are not single-parametric (e.g. in <a href="Combinatorial_auction" title="Combinatorial auction">combinatorial auctions</a>), the mechanism design problem is much more complicated. The <a href="VCG_mechanism" class="mw-redirect" title="VCG mechanism">VCG mechanism</a> is one of the only mechanisms that works for such general valuations.

<ul><li><a href="Single_peaked_preferences" title="Single peaked preferences">Single peaked preferences</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFVaziraniNisanRoughgardenTardos2007" class="citation book cs1"><a href="Vijay_Vazirani" title="Vijay Vazirani">Vazirani, Vijay V.</a>; <a href="Noam_Nisan" title="Noam Nisan">Nisan, Noam</a>; <a href="Tim_Roughgarden" title="Tim Roughgarden">Roughgarden, Tim</a>; <a href="%C3%89va_Tardos" title="Éva Tardos">Tardos, Éva</a> (2007). <a rel="nofollow" class="external text" href="http://www.cs.cmu.edu/~sandholm/cs15-892F13/algorithmic-game-theory.pdf">Algorithmic Game Theory</a> (PDF). Cambridge, UK: Cambridge University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-521-87282-0</bdi>.</cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2022-10-02" href="https://en.wikipedia.org/wiki/?title=Single-parameter_utility&oldid=1113708626">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>